A compiler enhances the execution efficiency of a program by causing registers to hold values of variables used in the program. A technique for allowing a compiler to determine which register to hold each of variables is referred to as register allocation. If a certain register is caused to consistently hold a certain variable used in a program through the register allocation, the register is occupied by the variable even during the execution of a part of the program not using the variable frequently. As a result, this register cannot be used for another purpose, so that the execution efficiency of the program is sometimes decreased as a whole.
To solve this problem, a compiler may split a variable in a program into new multiple variables respectively corresponding to parts of the program, for example. Then, the complier selectively determines whether or not a register is allocated to each of the multiple variables. Thereby, the register can be used for another purpose even during the execution of a part of the program not using the variable frequently, and this enhances the execution efficiency of the program. On the other hand, when the variable is split into the new multiple variables, it is necessary to perform a process of assigning the value from one to a subsequent one of the new multiple variables. If this assigning process needs to be performed too many times, the execution efficiency of the program is decreased. For this reason, it is preferable to split a variable to an appropriate extent in order to enhance the execution efficiency of the program as a whole.
In order to split a variable to an appropriate extent, one may come up with an idea of applying a technique of merging nodes in a graph with each variable expressed as a node and with each interference relationship between variables expressed as an edge. However, use of known techniques described results in insufficient coalescing, so that too many assignment instructions are generated in some cases. In addition, use of known techniques described results in excessive coalescing and accordingly fails to produce a sufficient degree of effect of splitting variables.
“Register Allocation Via Graph Coloring,” discloses a series of improvements and extensions to the first built global register allocator based on graph coloring built by Chaitin. The thesis discloses four primary results: (1) Optimistic coloring: The first built global register allocator assumes any node of high degree will not be colored and must therefore be spilled. By optimistically assuming that nodes of high degree will receive colors, lower spill costs and faster code are often achieved; (2) Coloring pairs: The pessimism of the first built global register allocator coloring heuristic is emphasized when trying to color register pairs. The thesis discloses pairs as a natural consequence of its optimism; (3) Rematerialization: The first built global register allocator introduced the idea of rematerialization to avoid the expense of spilling and reloading certain simple values. By propagating rematerialization information around the SSA graph using a simple variation of Wegman and Zadeck's constant propagation techniques, the thesis discovers and isolates a larger class of such simple values; (4) Live range splitting: Chow and Hennessy's technique, priority-based coloring, includes a form of live range splitting. By aggressively splitting live ranges at selected points before coloring, the thesis disclosure is able to incorporate live range splitting into the framework of the first built global register allocator. The thesis discloses the results of experimental studies measuring the effectiveness of each of the disclosures improvements. The thesis further discloses the results of an experiment suggesting that priority-based coloring requires O($n\sp2$) time and that the Yorktown allocator requires only O(n log n) time. The thesis disclosure includes a chapter describing many implementation details and including further measurements designed to provide an accurate intuition about the time and space requirements of coloring allocators.
“Register Allocation & Spilling Via Graph Coloring,” discloses how to extend the use of graph coloring techniques for doing global register allocation in a PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time so that it naturally solves the spilling problem. The thesis discloses how spill decisions are made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. The thesis discloses that the new approach produces better object code and takes much less compile time.
“Iterated Register Coalescing,” disclose that an important function of any register allocator is to target registers so as to eliminate copy instructions. The thesis discloses that a graph-coloring register allocation is an elegant approach to this problem. The thesis discloses that If the source and destination of a move instruction do not interfere, then their nodes can be coalesced in the interference graph. The thesis discloses that Chaitin's coalescing heuristic could make a graph uncolorable (i.e., introduce spills), Briggs et al. demonstrated a conservative coalescing heuristic that preserves colorability. The thesis discloses that Brigg's algorithm is too conservative and leaves too many move instructions in our programs. The thesis discloses that it has discovered how to interleave coloring reductions with Brigg's coalescing heuristic, leading to an algorithm that is safe but much more aggressive.
“Improvements to Graph Coloring Register Allocation,” discloses that the thesis describes two improvements to Chaitin-style graph coloring register allocators. The thesis discloses that the first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The thesis discloses that the second extends Chaitin's treatment of rematerialization to handle a larger class of values and that these techniques are complementary. The thesis discloses that optimistic coloring decreases the number of procedures that require spill code and reduces the amount of spill code when spilhng is unavoidable and that rematerialization lowers the cost of spilhng some values. The thesis discloses that: both of the techniques and the experience building and using register allocators that incorporate them; provides a detailed description of optimistic coloring and rematerialization; presents experimental data to show the performance of several versions of the register allocator on a suite of FORTRAN programs; and discusses several insights that we discovered only after repeated implementation of these allocators.
“Optimistic Register Coalescing,” discloses that graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. The thesis discloses that coalescing can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. The thesis discloses that unlike aggressive coalescing, which coalesces any pair of noninterfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. The thesis discloses that these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. The thesis further discloses that they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. The thesis proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. The thesis discloses that since there is a better chance of coloring one of those splits, the disclosure can reduce the overall spill amount.
Against this background, an object of the present invention is to provide a compiler apparatus and a compiling method and program capable of solving the foregoing problems. This object can be achieved by using a combination of features described in the independent claims in the scope of claims. In addition, the dependent claims define more advantageous specific examples of the present invention.